#include <stdio.h>
#include <stdlib.h>

typedef int bitstr;
#define bits_num (sizeof(bitstr)<<3)

inline void set_bit(bitstr *msg, int i)
{
     *msg |= 1 << (bits_num - i);
}

inline void clr_bit(bitstr *msg, int i)
{
     *msg &= ~(1 << (bits_num - i));
}

inline void inv_bit(bitstr *msg, int i)
{
     *msg ^= (1 << (bits_num - i));
}

inline int tst_bit(bitstr *msg, int i)
{
     return *msg & (1 << (bits_num - i));
}

inline shift_right_from(bitstr *msg, int i)
{
     int b, a;

     /* For i == 1, shift left by 32 is undefined. */
     if (i == 1)
	  *msg = (unsigned int)(*msg) >> 1;
     else{
	  b = *msg & ((1 << (bits_num-i+1))-1);
	  a = *msg & ~((1 << (bits_num-i+1))-1);
	  *msg = ((unsigned int)b >> 1) | a;
     }
}

inline shift_left_from(bitstr *msg, int i)
{
     int b, a;

     /* For i == 1, shift left by 32 is undefined. */
     if (i == 1)
	  *msg = (unsigned int)(*msg) << 1;
     else{
	  b = *msg & ((1 << (bits_num-i+1))-1);
	  a = *msg & ~((1 << (bits_num-i+1))-1);
	  *msg = (b << 1) | a;
     }
}

inline print_bits(bitstr *msg, int k)
{
     int i, x;

     for (i = 1; i <= k; i++){
	  x = tst_bit(msg, i);
	  if (x)
	       printf("%d", 1);
	  else
	       printf("%d", 0);
     }
     printf("\n");
}

int code(int *msg, int k)
{
     int i, j, r;

     /*
       There are m message bits and r check bits in a codeword.
       The m is already known, while the r should be searched. 
      */
     r = 1;
     while ((1<<r) < k+r+1)
	  r++;

     /*
       rewrite the codeword.
      */
     i = 1;
     for (j = 1; j <= k+r; j++){
	  if (j == i){
	       shift_right_from(msg, j);
	       i <<= 1;
	  }
     }

     /* 
	Fill up check bits.
      */
     for (i = 0; i < r; i++){
	  int e, x;
	  e = 1 << i;
	  x = 0;
	  for (j = e+1; j <= k+r; j++){
	       if (j & e)
		    x ^= tst_bit(msg, j) ? 1 : 0;
	  }
	  if (x)
	       set_bit(msg, e);
	  else 
	       clr_bit(msg, e);
     }
}

void transfer(int *msg, int k, int r)
{
     inv_bit(msg, 4);
}

void decode(int *msg, int k, int r)
{
     int i, j, p;

     /* Check whether there is an error. */
     p = 0;
     for (i = 0; i < r; i++){
	  int e, x;
	  e = 1 << i;
	  x = 0;
	  for (j = e; j <= k+r; j++){
	       if (j & e)
		    x ^= tst_bit(msg, j) ? 1 : 0;
	  }
	  if (x)
	       p += e;
     }

     /* If an error occur, correct it */
     if (p)
	  inv_bit(msg, p);

     i = 1 << (r-1);
     for (j = k+r; j >= 1; j--){
	  if (j == i){
	       shift_left_from(msg, j);
	       i >>= 1; // i can not turn into negtive
	  }
     }
}

int main()
{
     FILE *fp;
     int msg, m, r;
     int i;
     char c;

     fp = fopen("hamming.in", "r");
     if (!fp){
	  fprintf(stderr, "Can not open hamming.in.\n");
	  exit(-1);
     }
     msg = 0;
     fscanf(fp, "%d\n", &m);
     for (i = 1; i <= m; i++){
	  fscanf(fp, "%c", &c);
	  if (c == '1') 
	       set_bit(&msg, i);
     }

     printf("Orininal: \t");
     print_bits(&msg, m);
     r = code(&msg, m);
     printf("Coded: \t\t");
     print_bits(&msg, m+r);
     transfer(&msg, m, r);
     printf("Received: \t");
     print_bits(&msg, m+r);
     decode(&msg, m, r);
     printf("Decoded: \t");
     print_bits(&msg, m);
     return 0;
}

